package com.wawayaya.bookreader.bean;


import com.wawayaya.util.TLog;

public class BTree<Key extends Comparable<Key>, Value> implements java.io.Serializable {

	private static final long serialVersionUID = 1L;

	private static final int M = 4;    // max children per B-tree node = M-1

    private Node root = null;             // root of the B-tree
    private int HT;                // height of the B-tree
    private int N;                 // number of key-value pairs in the B-tree

    // helper B-tree node data type
    private static final class Node implements java.io.Serializable {
    	private static final long serialVersionUID = 4L;
        private int m;                             // number of children
        private Entry[] children = new Entry[M];   // the array of children
        private Node(int k) { 
        	// create a node with k children
        	m = k; 
        }             
    }

    // internal nodes: only use key and next
    // external nodes: only use key and value
    private static class Entry implements java.io.Serializable {
    	
    	private static final long serialVersionUID = 5L;
    	
        private Comparable<?> key;
        private Object value;
        private Node next;     // helper field to iterate over array entries
        public Entry(Comparable<?> key, Object value, Node next) {
            this.key   = key;
            this.value = value;
            this.next  = next;
        }
    }

    // constructor
    public BTree() { root = new Node(0); }
 
    // return number of key-value pairs in the B-tree
    public int size() {
    	return N; 
    }

    // return height of B-tree
    public int height() {
    	return HT; 
    }

    // search for given key, return associated value; return null if no such key
    public Value getValue(Key key) {
    	return search(root, key, HT); 
    }
    
    private Value search(Node x, Key key, int ht) {
        Entry[] children = x.children;

        // external node
        if (ht == 0) {
            for (int j = 0; j < x.m; j++) {
                if (eq(key, children[j].key)){
                	return (Value) children[j].value;
                }
            }
        }

        // internal node
        else {
            for (int j = 0; j < x.m; j++) {
                if (j+1 == x.m || less(key, children[j+1].key)){
                    return search(children[j].next, key, ht-1);
                }
            }
        }
        return null;
    }

    public Key getkey(Key key) {
    	return searchkey(root, key, HT); 
    }
    
    private Key searchkey(Node x, Key key, int ht) {
        Entry[] children = x.children;

        // external node
        if (ht == 0) {
            for (int j = 0; j < x.m; j++) {
                if (eq(key, children[j].key)){
                	return (Key) children[j].key;
                }
            }
        }

        // internal node
        else {
            for (int j = 0; j < x.m; j++) {
                if (j+1 == x.m || less(key, children[j+1].key)){
                    return searchkey(children[j].next, key, ht-1);
                }
            }
        }
        return null;
    }

    // insert key-value pair
    // add code to check for duplicate keys
    public void put(Key key, Value value) {
        Node u = insert(root, key, value, HT); 
        N++;
        if (u == null) return;

        // need to split root
        Node t = new Node(2);
        t.children[0] = new Entry(root.children[0].key, null, root);
        t.children[1] = new Entry(u.children[0].key, null, u);
        root = t;
        HT++;
    }


    private Node insert(Node h, Key key, Value value, int ht) {
        int j;
        Entry t = new Entry(key, value, null);

        // external node
        if (ht == 0) {
            for (j = 0; j < h.m; j++) {
                if (less(key, h.children[j].key)) {
                	break;
                }
            }
        }

        // internal node
        else {
            for (j = 0; j < h.m; j++) {
                if ((j+1 == h.m) || less(key, h.children[j+1].key)) {
                    Node u = insert(h.children[j++].next, key, value, ht-1);
                    if (u == null) return null;
                    t.key = u.children[0].key;
                    t.next = u;
                    break;
                }
            }
        }

        for (int i = h.m; i > j; i--) {
        	h.children[i] = h.children[i-1];
        }
        h.children[j] = t;
        h.m++;
        if (h.m < M) {
        	return null;
        }
        return split(h);
    }

    // split node in half
    private Node split(Node h) {
        Node t = new Node(M/2);
        h.m = M/2;
        for (int j = 0; j < M/2; j++)
            t.children[j] = h.children[M/2+j]; 
        return t;    
    }

    // for debugging
    public String toString() {
        return toString(root, HT, "") + "\n";
    }
    private String toString(Node h, int ht, String indent) {
        String s = "";
        Entry[] children = h.children;

        if (ht == 0) {
            for (int j = 0; j < h.m; j++) {
                s += indent + children[j].key + " " + children[j].value + "\n";
            }
        }
        else {
            for (int j = 0; j < h.m; j++) {
                if (j > 0) s += indent + "(" + children[j].key + ")\n";
                s += toString(children[j].next, ht-1, indent + "     ");
            }
        }
        return s;
    }


    // comparison functions - make Comparable instead of Key to avoid casts
    private boolean less(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) < 0;
    }

    private boolean eq(Comparable k1, Comparable k2) {
        return k1.compareTo(k2) == 0;
    }    
    
    public int enumerate() {
    	if(TLog.DEBUG && null != root) {
			internalenumerate(root, "");
			return size();
    	}
    	return 0;
    }
    private void internalenumerate(Node rt, String sprefix) {
		if(null != rt) {
    		Entry[] children = rt.children;
    		if(null != children) {
    			for(Entry child : children) {
    				if(null != child) {
        				PosRegionKey rk = (PosRegionKey)child.key;
        				DictData dd = (DictData)child.value;
        				if(null != rk){
        					String s = sprefix + " : (" + rk.getleft() + ", " + rk.gettop() + ", " + rk.getright() + ", " + rk.getbottom() + ")";
        					if(null != dd){
        						s += " : " + dd.m_character;
        					}
        					TLog.log(s);
        				}
        				if(null != child.next){
        					internalenumerate(child.next, sprefix + "-");
        				}
    				}
    			}
    		}
		}
    }
    
}
